NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part2/17663

Internet Message Format | 1996-08-05 | 3.3 KB

Path: news.cyberport.com!usenet
From: [e-mail] (Warren Young)
Newsgroups: comp.lang.c++
Subject: Re: STL: tiny vectors
Date: Wed, 17 Apr 1996 00:20:43 GMT
Organization: none
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: ppp4.cyberport.com
X-Newsreader: Forte Agent .99d/32.182

[e-mail] (Doug Wyatt) wrote:

>Many of my vectors are rather small, 2-10 small elements.  The
>implementation of allocator (HP via Metrowerks CodeWarrior) implements
>memory in chunks of no less than 4096 bytes.  When I have many arrays
>under 100 bytes, this adds up to a lot of wasted memory.
>
>I started writing code to make my algorithms multi-pass so I can know in
>advance how large a vector is to be, and call reserve(), but it seems this
>really shouldn't be necessary.

As I recall, HP STL will only allocate as much space as it needs if
you use the ctor with an integer size parameter (I think it's just
vector(int)).  Again, though, this requires that you know something
about your data ahead of time.

The thing is, though, the allocation policies are up to the container,
not a part of the standard at all.  So, you should be able to change
the implementation in this regard and still have a "legal" STL.

>Another thing I've toyed with is using my own allocator which uses
>malloc() and free() instead of the global operators new and delete.  That
>way I can use realloc() to shrink a vector.  I suppose this will work but

Be careful with this, because this can move the data around in memory.
So, you can only do it when the vector would have been modified
anyway.  Consider what would happen if the user had some iterators
into the vector and you realloc'd it.

Another potential problem: when you realloc memory, the data is moved
with a bitwise copy.  This can cause real trouble, especially with
contained classes that depend on their operator= or copy ctor getting
called when they are moved.  Dangling pointers is just the beginning.
Don't get me wrong...this will often work correctly, such as with
built-in types and those classes that can successfully work with the
copy ctor implicitly generated by the compiler when you don't supply
one.

Anyway, you _can_ reallocate memory with new and delete, and in the
same fashion, it's just not as clean: new the new block, copy the data
over, and delete the old block.  realloc() does the same thing (or at
least, it can), it's just a single call instead of three.

>I have a book that claims the default allocator should be using a page
>size of 512, so perhaps making my own allocator use 512 would be a simple

Again, the STL's pre-allocation policy isn't spec'd in the standard.
Would this happen to be Nelson's STL book?  If so, note that he only
deals with vanilla HP STL in the book, so he can reasonably talk about
such implementation details.

>Should I be using another container besides vector?  I thought about using
>a list but I'd like to be able to retain fast random access into my
>containers.

If I were you, I'd hack a vector<T> to do what you want it to.  If you
stick with the same class interface, you should even be able to drop
it in with minimal changes.  I'd change the container's name, though.

Or, find someone else's dynamic vector implementation that you like
better, if STL compatibility isn't too big an issue for you.

= Warren --